#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 7
typedef int ElemType;
typedef struct SSTable {
    ElemType lenth;
    ElemType *str;
} SSTable;

void SST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
//    int a[10]={3,87,2,93,78,56,61,38,12,40};
//    memcpy(T.str,a,sizeof(a));
    srand(time(NULL));
    for (int i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;
    }
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

//合并两个有序数组
void Merge(ElemType *str, ElemType low, ElemType mid, ElemType high) {
    static ElemType arr[N];//加static的目的是无论递归调用多少次，都只有一个arr[N]
    int i, j, k;
    for (i = low; i <= high; i++) {//把str[i]中的元素都给arr[i]
        arr[i] = str[i];
    }
    k = low;
    for (i = low, j = mid + 1; i <= mid && j <= high; k++) {//合并两个有序数组
        if (arr[i] < arr[j]) {
            str[k] = arr[i++];
        } else {
            str[k] = arr[j++];
        }
    }
    //把某一个有序数组中剩余的元素放进来
    while (i <= mid) {//如果有剩余元素，接着放入即可
        str[k++] = arr[i++];//前一半的有剩余的放入
    }
    while (j <= high) {
        str[k++] = arr[j++];//后一半的有剩余的放入
    }
}

//归并排序不限制时两两归并，还是多个归并，考研都是考两两归并
void MergeSort(ElemType *str, ElemType low, ElemType high) {//递归切割
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(str, low, mid);//排序好前一半
        MergeSort(str, mid + 1, high);//排序好后一半
        Merge(str, low, mid, high);//将两个排序好的数组合并
    }
}

//归并排序
int main() {
    SSTable T;
    SST_Init(T, N);
    array_print(T);
    MergeSort(T.str, 0, T.lenth);
    array_print(T);
    return 0;
}
